/*
 * Copyright (c) 2021.版权所有高金磊
 */

package 领扣算法.AA中等题.对链表进行插入排序;

public class Main {

    public ListNode insertionSortList(ListNode head) {
        ListNode listNode=head;//已经有序的头结点
        head=head.next;
        listNode.next=null;
        while (head!=null){
            //插入head结点
            ListNode middle=head.next;
            head.next=null;
            listNode=plus(listNode,head);
            head=middle;
        }
        return listNode;
    }

    private ListNode plus(ListNode listNode, ListNode head) {
        if (listNode.val>head.val){
            head.next=listNode;
            return head;
        }
        ListNode middle=listNode;
        while (middle.next!=null&&head.val>middle.next.val){
            middle=middle.next;
        }
        head.next=middle.next;
        middle.next=head;
        return listNode;
    }
}
class ListNode {
      int val;
      ListNode next;
      ListNode() {}
     ListNode(int val) { this.val = val; }
     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 }
